import sys
import os
sys.path.insert(0, os.path.join(os.path.dirname(os.path.dirname(os.path.abspath(__file__)))))

from DataStructure.single_link_list import SingleLinkList


# 不创建新节点的情况下完成链表的合并, 但会变改原链表的数据
def single_link_list_merge(la, lb):
    tmp_la = la.head
    tmp_lb = lb.head
    lc = tmp_lc = la
    while tmp_la and tmp_lb:
        if tmp_la.item <= tmp_lb.item:
            if lc.length() < 1:
                tmp_lc.head = tmp_la
            else:
                tmp_lc.next = tmp_la
            tmp_lc = tmp_la
            tmp_la = tmp_la.next
        else:
            if lc.length() < 1:
                tmp_lc.head = tmp_lb
            else:
                tmp_lc.next = tmp_lb
            tmp_lc = tmp_lb
            tmp_lb = tmp_lb.next
    tmp_lc.next = tmp_la if tmp_la else tmp_lb
    lb.head = None
    # la.head = None
    return lc


# 创建新节点完成链表的合并, 不影响原链表的数据
def single_link_list_merge1(la, lb, lc):
    la = la.head
    lb = lb.head
    while la and lb:
        if la.item <= lb.item:
            lc.append(la.item)
            la = la.next
        else:
            lc.append(lb.item)
            lb = lb.next
    tmp = la if la else lb
    while tmp:
        lc.append(tmp.item)
        tmp = tmp.next


if __name__ == "__main__":
    la = SingleLinkList()
    lb = SingleLinkList()
    for i in ["a", "c", "f", "g"]:
        la.append(i)
    for i in ["b", "d", "e", "l", "m"]:
        lb.append(i)
    # print(la.head)
    # 把两个有序的链表重新组成一个新的有序的链表
    lc = single_link_list_merge(la, lb)
    # single_link_list_merge1(la, lb)
    la.travel()
    lb.travel()
    lc.travel()

